| 翻訳と辞書 |
| trapezoid graph ： ウィキペディア英語版 |
trapezoid graph
In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988. There exists algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.
== Definitions and characterizations ==
Given a channel, a pair of two horizontal lines, a trapezoid between these lines is defined by two points on the top and two points on the bottom line. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect.
The interval order dimension of a partially ordered set, , is the minimum number d of interval orders P1 … Pd such that P = P1∩…∩Pd. The incomparability graph of a partially ordered set is the undirected graph where ''x'' is adjacent to ''y'' in G if and only if ''x'' and ''y'' are incomparable in P. An undirected graph is a trapezoid graph if and only if it is the incomparability graph of a partial order having interval order dimension at most 2.〔Ido Dagan, Martin Charles Golumbic, and Ron Yair Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 35–46, 1988.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「trapezoid graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|